/**
 * Created:	2011-8-16
 * By:		eeorange
 * OS:		Windows/mingw
 * Ques ID:	1027 Human Gene Functions
 * Status:	20ms
 * Desc:	DP problem. use map to store dynamic data. start from dp(na, nb)x
 *
 */
#ifdef ONLINE_JUDGE
	#define NDEBUG
#endif
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;

const int MAXN = 100 + 10;
const int INF = 100000000;

char DA[MAXN], DB[MAXN];		// input data
char A[MAXN*2], B[MAXN*2];	// temp data
int na, nb;
int ans;
map<pair<int, int>, int> vis;

const int M[5][5] = {
	{5, -1, -2, -1, -3},
	{-1, 5, -3, -2, -4},
	{-2, -3, 5, -2, -2},
	{-1, -2, -2, 5, -1},
	{-3, -4, -2, -1, 1000}};

int cal(char a, char b){
	int x, y;
	static const string gene = "ACGT-";
	x = gene.find(a);
	y = gene.find(b);

	assert(x >= 0 && x < 5 && y >= 0 && y < 5);
	return M[x][y];
}

// ai, bi start from na and nb
int dp(int ai, int bi)
{
	pair<int, int> p = make_pair(ai, bi);
	if(vis.count(p) != 0) return vis[p];
	if(ai || bi)
	{
		int s = -INF;
		if(ai > 0) s = max(s, dp(ai-1, bi) + cal(DA[ai-1], '-'));
		if(bi > 0) s = max(s, dp(ai, bi-1) + cal('-', DB[bi-1]));
		if(ai && bi) s = max(s, dp(ai-1, bi-1) + cal(DA[ai-1], DB[bi-1]));
		return vis[p] = s;
	}
	else return 0;
}
/*
void dp(int cur, int ai, int bi)
{
	if(ai == na && bi == nb)
	{
		A[cur] = B[cur] = 0;
		int s = 0;
		for(int x=0; x < cur; x++) s += cal(A[x], B[x]);
		if(ans < s) ans = s;
	}
	else{
		if(bi < nb){
			A[cur] = '-';
			B[cur] = DB[bi];
			dp(cur+1, ai, bi+1);
		}
		if(ai < na){
			A[cur] = DA[ai];
			B[cur] = '-';
			dp(cur+1, ai+1, bi);
		}
		if(ai < na && bi < nb){
			A[cur] = DA[ai];
			B[cur] = DB[bi];
			dp(cur+1, ai+1, bi+1);
		}
	}
}
*/
int main(){
	#ifndef ONLINE_JUDGE
		freopen("data.in", "r", stdin);
	#endif
	
	int nca;
	cin >> nca;
	while(nca--)
	{
		string line;
		cin >> na >> line;
		for(int i=0; i < na; i++) DA[i] = line[i];

		cin >> nb >> line;
		for(int i=0; i < nb; i++) DB[i] = line[i];
		
		vis.clear();
		cout << dp(na, nb) << endl;
	}


	#ifndef ONLINE_JUDGE
		printf("Time used = %.3lf\n", (double)clock()/CLOCKS_PER_SEC);
	#endif
	return 0;
}

